package com.gxc.linkedList;

import java.util.Stack;

/**
 * 两个单链表生成相加链表
 */
public class AddList {

    /**
     * 使用额外空间
     * @param head1
     * @param head2
     * @return
     */
    public ListNode handle(ListNode head1, ListNode head2) {
        Stack<ListNode> stack1 = new Stack<>();
        ListNode node = head1;
        while (node != null) {
            stack1.push(node);
            node = node.next;
        }
        Stack<ListNode> stack2 = new Stack<>();
        node = head2;
        while (node != null) {
            stack2.push(node);
            node = node.next;
        }

        boolean carry = false;
        ListNode pre = null;
        int a = 0;
        int b = 0;
        int sum = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            a = stack1.isEmpty()?0:stack1.pop().val;
            b = stack1.isEmpty()?0:stack2.pop().val;
            sum = a + b + (carry?1:0);
            carry = false;
            if (sum>9) {
                carry = true;
                sum = sum - 10;
            }
            ListNode listNode = new ListNode(sum);
            listNode.next = pre;
            pre = listNode;
        }
        if (carry) {
            ListNode listNode = new ListNode(1);
            listNode.next = pre;
            pre = listNode;
        }
        return pre;
    }

    /**
     * 不使用额外空间
     * @param head1
     * @param head2
     * @return
     */
    public ListNode handle2(ListNode head1, ListNode head2) {
        //逆序
        head1 = reverse(head1);
        head2 = reverse(head2);

        ListNode h1 = head1;
        ListNode h2 = head2;
        int ca = 0;
        int n1 = 0;
        int n2 = 0;
        int sum = 0;

        ListNode node = null;
        ListNode pre = null;
        while (h1 != null || h2 != null) {
            n1 = h1 == null ?0:h1.val;
            n2 = h2 == null?0:h2.val;
            sum = n1 + n2 + ca;
            ca = sum/10;
            node = new ListNode(sum % 10);
            node.next = pre;
            pre = node;

            h1 = h1 == null ? null:h1.next;
            h2 = h2 == null ? null:h2.next;
        }
        if (ca == 1) {
            node = new ListNode(sum - ca * 10);
            node.next = pre;
            pre = node;
        }

        //逆序
        head1 = reverse(head1);
        head2 = reverse(head2);

        return pre;
    }

    /**
     * 逆序链表
     * @param head
     * @return
     */
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public static class ListNode {
        int val;
        AddList.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, AddList.ListNode next) { this.val = val; this.next = next; }
    }
}
